package com.yiwenup.leetcode.hot;

import java.util.ArrayList;
import java.util.List;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.hot
 * @Author yiwenup
 * @Date 2022-03-09 21:08:13
 * <p>
 * @DESCRIPTION https://leetcode-cn.com/problems/combination-sum/
 * <pre>
 *     输入：candidates = [2,3,6,7], target = 7
 *     输出：[[2,2,3],[7]]
 *     解释：
 *     2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 *     7 也是一个候选， 7 = 7
 * </pre>
 */
public class No0039 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();

        dfs(candidates, target, res, tmp, 0);

        return res;
    }

    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了96.45%的用户
     * 内存消耗：41.5 MB, 在所有 Java 提交中击败了38.53%的用户
     */
    private void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> tmp, int idx) {
        if (idx == candidates.length) return;
        if (target == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        dfs(candidates, target, res, tmp, idx + 1);
        if (target - candidates[idx] >= 0) {
            tmp.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], res, tmp, idx);
            tmp.remove(tmp.size() - 1);
        }
    }
}
